package flashBack;

/**
 * @author zxc
 * @date 2023/01/16 11:33
 **/

import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：允许重复选择元素的组合
 * 题目详述 ：
 * 给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
 * candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
 *
 * 提示：
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * candidate 中的每个元素都是独一无二的。
 * 1 <= target <= 500
 */
public class CombinationSum {
    /**
     *  思路 ：
     *  （1）使用result集合，来存储所有可能的结果;
     *  （2）回溯法 ：即，对于数组下标为index的数组元素进行选择（是否将其加入到candidate子集合中）
     *  flushBackRepeat(candidates , target , 0 , new LinkedList<Integer>() , result);
     *  （3）所调用的回溯方法 ：即，如何来判断合适的子集合?
     *  即，target是否为0;（即，每次进行回溯时，若是选择将数组下标为index的数组元素进行插入的话，需要target = target - nums[index];）
     *  （4）同时，由于组合中允许存储nums数组中重复元素，
     *  所以若是不去进行遍历范围的限定的话，即可能会无穷无尽地进行元素遍历/选择;
     *  即，target > 0 && index < nums.length 条件进行限定，来进行回溯法的“剪枝”操作;
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();
        /**
         * 参数分析 ：
         * （1）第一个参数 ：即，初始数组candidates；（无重复的正整数数组candidates）;
         * （2）第二个参数 ：target，即目标值总和;
         * （3）第三个参数 ：即，所遍历数组元素的下标;
         * （4）第四个参数 ：即，list集合用来保持某个解状态;
         * （5）第五个参数 ：即，result集合数组，用来保持所有解状态;
         */
        flushBackRepeat(candidates , target , 0 , new LinkedList<Integer>() , result);
        return result;
    }
    // 回溯
    private void flushBackRepeat(int[] candidates, int target, int index, LinkedList<Integer> candidate, List<List<Integer>> result) {
        if(target == 0){
            // result集合中所添加的解状态，是candidate集合的拷贝；
            // 原因如下 ：
            // candidate集合后续还需要进行修改，为避免后续的修改操作，影响之前在result集合中所存储的所以解状态；
            // ===》 会选择将candidate集合的拷贝存储到result集合中;
            result.add(new LinkedList<>(candidate));
        }
        // 即，使用回溯法时避免遍历不必要子树的操作，被称为“剪枝”;
        // （1）target > 0条件判断，就为“剪枝”操作;
        //      即，若是当前组合中值的和 > target（反之，即target < 0），那么后续选择就没有意义了，因为必然是不成立的
        //      （无论后续排序选择加入/不加入，组合值 > target，会导致后面没有符合条件的组合，但是依然还在进行遍历和选择）
        // （2）index < candidates.length，即代表当前正在遍历的index下标的数组元素不存在于candidates数组中时，没有意义
        // ===> 由于组合可以容忍重复元素，所以不能够确认到底需要进行多少步选择;（若是不限制的话，可能会进行无穷步选择，导致timeout报错）
        // 必须同时满足上述两个条件，就可以实现若是组合中的值 > target && index >= candidates.length后，不会再继续进行遍历和选择;
        // (对比之下 ：若是组合不可以容忍重复元素的话，是能够去确认需要进行多少步选择的，所需要的选择数 ：原数组中的元素数量)
        else if(target > 0 && index < candidates.length){
            // index下标的数组元素candidates[index]，不选择将其插入到candidate集合中;
            // 同时，target不应该减去candidates[index]，保持原本的terget值即可;
            flushBackRepeat(candidates , target , index + 1 , candidate , result);

            // index下标的数组元素candidates[index],选择将其加入到candidate解状态集合中；
            // 同时，target也应该减去candidates[index];
            candidate.add(candidates[index]);
            // 所传入的target，会选择减去candidates[index];
            // 由于candidates数组中的元素可以在所要求的组合中重复出现，所以要去判断candidates[index]是否还选择加入到candidate解状态集合中;
            flushBackRepeat(candidates , target - candidates[index] , index , candidate , result);
            // 回溯到上一个数组元素时，需要将当前数组元素对于candidate解状态集合所进行的修改回溯;
            candidate.removeLast();
        }
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（2的n次方）
     */
}
